class Solution(object):
    def largestSumAfterKNegations(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        out = []
        t = 0
        for num in nums:
            if num < 0:
                out.append(- num)
            else:
                t += num
        if k <= len(out):
            out.sort(reverse=True)
            t += sum(out[:k])
            t -= sum(out[k:])
        else:
            t += sum(out)
            if (k - len(out)) % 2 == 1:
                nums = [abs(num) for num in nums]
                t -= 2 * min(nums)
        return t

data = Solution()
nums = [2,-3,-1,5,-4]
k = 2
print(data.largestSumAfterKNegations(nums, k))